import java.util.Arrays;

class Solution {
    public int numDecodings(String s) {
        int n=s.length();
        int[] dp=new int[n+1];
        if(s.charAt(0)=='0') return 0;
        dp[0]=1;
        for(int i=1;i<=n;i++){
            char c=s.charAt(i-1);
            if(c!='0') dp[i]+=dp[i-1];


            if(i>1){
                String ss=s.substring(i-2,i);
                if(ss.compareTo("26")<=0&&s.charAt(i-2)!='0'){
                    dp[i]+=dp[i-2];
                }
            }

        }
        return dp[n];
    }
}


class Solution1 {
    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != '0') {
                f[i] += f[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
}




class Solution2{
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m+1][n+1];
        dp[1][1]=1;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]+=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];
    }
}


//一维化dp数组
class Solution5 {
    public int uniquePaths(int m, int n) {
        // 使用一维数组dp，大小为n
        int[] dp = new int[n];
        // 初始化第一行，所有列的路径数都为1（因为只能从左边走过来）
        Arrays.fill(dp, 1);

        // 从第二行开始更新
        for (int i = 1; i < m; i++) {
            // 更新当前行的dp数组
            for (int j = 1; j < n; j++) {
                // dp[j]是上一行的值，dp[j-1]是当前行的值
                dp[j] += dp[j - 1];
            }
        }

        // 最后dp[n-1]就是到达右下角的路径数
        return dp[n - 1];
    }
}


class Solution3 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;


        int[][] dp=new int[m+1][n+1];
        if(obstacleGrid[0][0]==0)
            dp[1][1]=1;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){

                if(obstacleGrid[i-1][j-1]==1){
                    dp[i][j]=0;
                    continue;

                }
                dp[i][j]+=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];
    }
}


class Solution4 {
    public int jewelleryValue(int[][] frame) {
        int m=frame.length;
        int n=frame[0].length;

        int[][] dp=new int[m+1][n+1];

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
            }
        }
        return dp[m][n];
    }
}


class Solution6 {
    public int minFallingPathSum(int[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        int[][] dp=new int[m][n+2];

        for(int i=0;i<m;i++){
            dp[i][0]=0x3f3f3f3f;
            dp[i][n+1]=0x3f3f3f3f;
        }

        for(int i=1;i<=n;i++){
            dp[0][i]=matrix[0][i-1];
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i-1][j+1]))+matrix[i][j-1];
            }
        }




        int ret=0x3f3f3f3f;

        for(int i=1;i<=n;i++){
            ret=Math.min(ret,dp[m-1][i]);

        }
        return ret;
    }
}